#include <iostream>
#include <cstring>
using namespace std;

void Print_(int* arr,int len){
	for(int i = 0;i < len;i++){
		cout<<arr[i]<<"  ";
	}
	cout<<"tmp "<<endl;
}
void Merge(int* arr,int l,int m,int r){
	int tmp_size = r-l+1;
	int* tmp =new int[tmp_size];
	//memcpy(tmp,arr,tmp_size*sizeof(int));
	for(int i = l;i <=r;i++){
		tmp[i-l] = arr[i];
	}
	int i = l,j = m+1;
	for(int k = l;k <= r;k++){	//这是下标范围，所以能取到边界
		if(i > m){		//左边循环完
			arr[k] = tmp[j-l];
			j++;
		}
		else if(j > r){		//右边循环完
			arr[k] = tmp[i-l];
			i++;
		}
		else if(tmp[i-l] <= tmp[j-l]){
			arr[k] = tmp[i-l];
			i++;
		}
		else{
			arr[k] = tmp[j-l];
			j++;
		}
	}
	//Print_(arr,tmp_size);
	delete []tmp;
	tmp = NULL;
}
void MergeSort(int* arr,int l,int r){
	cout<<"deal with ["<<l<<"---"<<r<<"]"<<endl;
	if(l >= r){
		return ;
	}
	else{
		int m = (r+l)/2;		//(r+l)/2
		MergeSort(arr,l,m);
		MergeSort(arr,m+1,r);
		Merge(arr,l,m,r);
	}
}
void Print(int* arr,int len){
	for(int i = 0;i < len;i++){
		cout<<arr[i]<<"  ";
	}
	cout<<endl;
}
int main(int argc, char const *argv[])
{
	int arr[7] = {55,4,53,2,8,7,0};
	Print(arr,7);
	MergeSort(arr,0,6);
	Print(arr,7);
	return 0;
}
